class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>>ret;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        if(n<4) return ret;
        for(int d=n-1;d>=3;)
        {
            int numd=nums[d];
            for(int c=d-1;c>=2;)
            {
                //规定一个数
                int numc=nums[c];
                //下面用双指针算法开始寻找
                int a=0,b=c-1;
                long long int target1=(long long)target-numd-numc;
                while(a<b)
                {
                    if(nums[a]+nums[b]==target1)
                    {
                        int numa=nums[a];
                        int numb=nums[b];
                        vector<int> tem={numa,numb,numc,numd};
                        ret.push_back(tem);
                        //去重
                        while(a<b&&nums[a]==numa) a++;
                        while(a<b&&nums[b]==numb) b--;
                    }
                    else if(nums[a]+nums[b]>target1)
                    {
                        b--;
                    }
                    else
                    {
                        a++;
                    }
                }
                //去重
                while(c>=2&&nums[c]==numc) c--;

            }
            while(d>=3&&nums[d]==numd) d--;
        } 
        return ret;
    }
};